LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034
|
B.Sc. DEGREE EXAMINATION – MATHEMATICS
FIFTH SEMESTER – November 2008
MT 5407 – FORMAL LANGUAGES AND AUTOMATA
Date : 14-11-08 Dept. No. Max. : 100 Marks
Time : 9:00 – 12:00
SECTION A
Answer ALL the questions: (102=20)
- Define a context sensitive grammar.
- Show that the language L ={is accepted by the grammar
G= ({S},{a,b,c}P,S) where P consists of the productions S → , S → bc.
- Define concatenation of two languages.
- Check whether the families of Phrase structure language and Context sensitive language are closed under intersection. Justify your answer.
- Let G = (N, T, P, S), where N = {S,A}, T = {a, b} and P consists of the rules S → aAb,
S → abSb, S → a, A → bS, A → aAAb. Check whether the grammar is ambiguous or unambiguous.
- Define leftmost derivation.
- Define Chomsky normal form.
- Define Self embedding property.
- What is the difference between deterministic finite automaton and non-deterministic finite automaton?
- Draw the state diagram for the non-deterministic finite state automaton M = (K, I, , , F) where K = , I = {0,1}, F = {} and δ is defined as follows,
| δ | 0 | 1 |
SECTION B
Answer any FIVE questions: (5=40)
- (a) Give a context sensitive grammar to generate L = .
(b) Let L = . Show that L is generated by the regular grammar G = (N, T, P, S) where N = {S, A}, T = {a, b} and P consists of the rules S → aS, S → aA, A →bA, A →b.
- (a) Define regular grammar.
(b) Let L = Show that a Context free grammar generating L is given by
G = (N. T, P, S) where N = {S,A}, T = {a, b} and P consists of the following productions: S → aSb, S →aAb, A →bA, A →b.
- Prove that the families of Phrase structure language, Context sensitive language, Context free language and Regular language are closed under union and product.
- Prove that the families of Phrase structure language, Context sensitive language, Context free language and Regular language are closed under inverse homomorphism. Prove also that the family of Context free language is not closed under intersection.
- Show that the grammar G =where = { S, ,V,
= { They, are, flying, planes}, = { S → () , → They, (V) (,
V → are, , A →flying, V → (Aux) (P), Aux → are, → N, P → flying} and S is the start symbol, generates the language consisting of the sentence { They are flying planes}.
- Write a grammar in Chomsky normal form to generate L= .
- Let L be accepted by a non- deterministic finite automata. Then show that there exists a deterministic finite automaton that accepts L.
- Draw the state diagram for the following finite state automaton, M = (K, I, , , F) where K = {}, I = {a, b, c}, F = { is defined as follows,
| a | b | c | |
| Φ | |||
SECTION C
Answer any TWO questions: (220=40)
- (a) Let L = . Prove that a context free grammar generating L is
G = ( {S,A}, {a, b}, P, S) where P consists of the rules S → aSb, S → aAb, A → bAa,
A → ba.
(b) Define Kleene closure and reflection of the language L.
(c) Prove that the families of Phrase structure language, Context sensitive language, Context free language and Regular language are closed under reflection.
- (a) Let G = (N, T, P,S) where N = {S}, T = {a}, P = { S → SS, S → a}. Show that the grammar is ambiguous.
(b) Given a context free grammar G = (N, T, P,S), prove that there exists an equivalent context free grammar such that for each non-terminal A S in G,
= is infinite.
(c) Write the construction of a grammar in Greibach normal form.
- State and prove u-v theorem and illustrate it with example.
- Given a finite state automaton M, prove that there exists a right-linear grammar G such that L(G) is set accepted by M and illustrate it with an example for non-deterministic finite state automata.
Latest Govt Job & Exam Updates: